function Node2() {
  this.key = 0
  this.h  = 0
  this.left = null 
  this.right = null
}

const NTL = new Node2()

function Node(key =0, h=0, left = NTL, right = NTL) {
  this.key = key
  this.h  = h
  this.left = left
  this.right = right
}

function AVL(rootKey) {
  this.root = new Node(rootKey,1)
}

AVL.prototype.updatedHeight = function(root) {
  root.h = Math.max(root.left.h, root.right.h) + 1
  return 
}

AVL.prototype.insert = function(root, key) {
  if(root == NTL) return this.getNewNode(key)
  if(root.key == key) return root
  if(root.key > key) root.left = this.insert(root.left, key)
  else root.right = this.insert(root.right, key)
  this.updatedHeight(root)
  return this.root = this.maintain(root)
}

AVL.prototype.predeccessort = function(root) {
  let temp = root
  while(temp.right != NTL) temp = temp.right
  return temp
}

AVL.prototype.left_rotate = function(root) {
  // console.log(root.key)
  let newRoot = root.right
  root.right = newRoot.left
  newRoot.left = root
  this.updatedHeight(root) 
  this.updatedHeight(newRoot) 
  return newRoot
}

AVL.prototype.right_rotate = function(root) {
  let newRoot = root.left
  root.left = newRoot.right
  newRoot.right = root
  this.updatedHeight(root) 
  this.updatedHeight(newRoot) 
  return newRoot
}

AVL.prototype.maintain = function (root) {
  let temp = Math.max(root.left.h, root.right.h)
  if(Math.abs(root.left.h - root.right.h) < 2 || temp<2) return root
  if(root.left.h > root.right.h) {
    if(root.left.left.h < root.left.right.h) {
      // LR
      root.left = this.left_rotate(root.left)
    }
    // LL || LR
    root = this.right_rotate(root)
  } else {
    if(root.right.left.h > root.right.right.h) {
      // RL
      root.right = this.right_rotate(root.right)
    }
    // RL || RR
    root = this.left_rotate(root)
  }
  return root
}

AVL.prototype.erase = function(root, key) {
  if(root == NTL) return root
  if(root.key > key) {
    root.left = this.erase(root.left, key)
  } else if(root.key < key) {
    root.right = this.erase(root.right, key)
  } else {
    if(root.left == NTL || root.right == NTL) {
      let temp = root.left ? root.left : root.right
      root = NTL
      return temp
    } else {
      let temp = this.predeccessort(root.left)
      root.key = temp.key
      root.left = this.erase(root.left, temp.key)
    }
  }
  this.updatedHeight(root)
  return this.root = this.maintain(root)
}


AVL.prototype.getNewNode = function(key) {
  return new Node(key, 1)
}


// let temp = new AVL(5)

// temp.insert(temp.root,4)
// temp.insert(temp.root,3)
// temp.insert(temp.root,2)
// temp.insert(temp.root,1)

// temp.erase(temp.root,12)


let temp = new AVL(5)

temp.insert(temp.root,9)
temp.insert(temp.root,8)
temp.insert(temp.root,3)
temp.insert(temp.root,2)
temp.insert(temp.root,4)
temp.insert(temp.root,1)
temp.insert(temp.root,7)
// temp.erase(temp.root,3)
// temp.erase(temp.root,8)
// temp.erase(temp.root,1)



console.log(JSON.stringify(temp.root, null, 2))